#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF_MAX 99999

class Graph {
public:
	Graph(int vCount) : vCount_(vCount) {
		adj_ = vector<vector<Edge>>(vCount);
	}
	// 添加一条边(起点, 终点, 权重)
	void addEdge(int s, int e, int w) {
		if(s < vCount_ && s >= 0 && e < vCount_ && e >= 0) {
			adj_[s].emplace_back(s, e, w);
		}
		else {
			cout << "ADD EDGE ERROR!" << endl;
			exit(0);
		}
	}
	// 寻找从s到e的最优路径
	int dijkstra(int s, int e) {
		vector<int> parent(vCount_); // 存储临时最优路径上的前驱，用以寻找最优路径
		vector<Vertex> vertexes(vCount_);
		for(int i = 0; i < vCount_; ++i) {
			vertexes[i].id_ = i;
			vertexes[i].dist_ = INF_MAX;
		}

		// 按照顶点的距离建立优先队列，距离最小的处于队头
		struct cmp {
			bool operator() (const Vertex& v1, const Vertex& v2) {
				return v1.dist_ > v2.dist_;
			}
		};
		priority_queue<Vertex, vector<Vertex>, cmp> queue;

		// 标记从起点到该顶点的距离是否最优
		vector<bool> vis(vCount_, false);

		vertexes[s].dist_ = 0;
		queue.push(vertexes[s]);
		while (!queue.empty()) {
			Vertex minVertex = queue.top();
			queue.pop();
			if(minVertex.id_ == e) break;
			if(vis[minVertex.id_] == true) continue;
			vis[minVertex.id_] = true;
			// for:更新最距离最小的顶点相邻的所有顶点的距离
			for(int i = 0; i < adj_[minVertex.id_].size(); ++i) {
				Edge cur_edge = adj_[minVertex.id_].at(i);
				int nex_vid = cur_edge.eid_;
				if(!vis[nex_vid]) {
					if(minVertex.dist_ + cur_edge.w_ < vertexes[nex_vid].dist_) {
						vertexes[nex_vid].dist_ = minVertex.dist_ + cur_edge.w_;
						parent[nex_vid] = minVertex.id_;
						queue.push(vertexes[nex_vid]);
					}
				}
			}
		}

		printRoute(s, e, parent);
		cout << endl;
		return vertexes[e].dist_;
	}
	// 寻找从s到各点的最短距离
	void dijkstra(int s) {
		vector<int> parent(vCount_); // 用于存储临时最优路径
		vector<Vertex> vertexes(vCount_);
		for(int i = 0; i < vCount_; ++i) {
			vertexes[i].id_ = i;
			vertexes[i].dist_ = INF_MAX;
		}

		// 按照顶点的距离建立优先队列，距离最小的处于队头
		struct cmp {
			bool operator() (const Vertex& v1, const Vertex& v2) {
				return v1.dist_ > v2.dist_;
			}
		};
		priority_queue<Vertex, vector<Vertex>, cmp> queue;

		// 标记从起点到该顶点的距离是否最优
		vector<bool> vis(vCount_, false);

		vertexes[s].dist_ = 0;
		queue.push(vertexes[s]);
		while (!queue.empty()) {
			Vertex minVertex = queue.top();
			queue.pop();
			if(vis[minVertex.id_] == true) continue;
			vis[minVertex.id_] = true;
			// for:更新距离最小的顶点相邻的所有顶点的距离
			for(int i = 0; i < adj_[minVertex.id_].size(); ++i) {
				Edge cur_edge = adj_[minVertex.id_].at(i);
				int nex_vid = cur_edge.eid_;
				if(!vis[nex_vid]) {
					if(minVertex.dist_ + cur_edge.w_ < vertexes[nex_vid].dist_) {
						vertexes[nex_vid].dist_ = minVertex.dist_ + cur_edge.w_;
						parent[nex_vid] = minVertex.id_;
						queue.push(vertexes[nex_vid]);
					}
				}
			}
		}
		cout << "The shortest distance from " << s + 1 << " to each vertex: ";
		for(int i = 0; i < vCount_; ++i) {		
			cout << vertexes[i].dist_ << " ";	
		}
		cout << endl;
	}

private:
	// 边的数据结构
	struct Edge {
		int sid_; // 边的起点
		int eid_; // 边的终点
		int w_;	// 边的权重
		Edge() = default;
		Edge(int s, int e, int w) : sid_(s), eid_(e), w_(w) {}
	};
	// 顶点的数据结构，在Graph内部顶点从0开始编号
	struct Vertex {
		int id_; // 顶点编号
		int dist_; // 暂存起点到该顶点的距离
		Vertex() = default;
		Vertex(int id, int dist) : id_(id), dist_(dist) {}
	};
	vector<vector<Edge>> adj_; // 邻接表数据结构
	int vCount_; // 顶点数

	// 打印最优路径
	void printRoute(int s, int e, const vector<int>& parent) {
		if(s == e) {
			cout << s + 1;
			return;
		}
		printRoute(s, parent[e], parent);
		cout << "->" << e + 1;
	}
};